A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, the computing devices (which may be referred to as network devices) communicate data by dividing the data into small blocks called packets. The packets are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
For a number of reasons, various network devices throughout the network monitor network traffic to detect patterns within the network traffic. Such devices may perform a form of packet inspection referred to as Deep Packet Inspection (DPI) that involves inspecting the payload or data portion of each packet as well as possibly a header or control portion of each packet across one or more layers of the Open Systems Interconnection (OSI) model. For example, an intermediate network device, such as a network security device referred to as an Intrusion Detection and Prevention (IDP) device, positioned between the source and destination device may perform DPI to determine whether the packets contains patterns indicative of a malicious attack. Upon detecting one of these patterns, the IDP device may detect and possibly prevent the malicious attack.
The pattern matching performed by the IDP devices often requires processing of complex data structures that can consume significant system resources. For example, one way to implement pattern matching involves a finite state machine referred to as a Deterministic Finite Automata (DFA). In general, each DFA is a finite state machine where for each pair of state and input symbol there is one and only one transition to a next state. A matching engine extracts symbols from packets and applies one or more DFAs to detect specified patterns within symbols carried by the network traffic.